package algorithms.roughgarden.part2.clustering;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

import com.notion.algorithms.datastructures.MinHeapAdapter;
import com.notion.algorithms.datastructures.UnionFind;
import com.notion.algorithms.datastructures.UnionFindable;

public class Main {
	private static List<Vertex> vertices = new ArrayList<Vertex>();
	private static List<Edge> mst = new ArrayList<Edge>();
	private static int noOfConnectedComponents;
	private static final int kClusterNumber = 4;

	public static void main(String[] args) throws IOException {
		UnionFind<Vertex> uf = new UnionFind<Vertex>();
		InputStream is = Main.class.getResourceAsStream("clustering1.txt.bak");
		BufferedReader br = new BufferedReader(new InputStreamReader(is));
		String str;
		str = br.readLine();
		noOfConnectedComponents = Integer.parseInt(str);

		for(int i=0;i<noOfConnectedComponents;i++){
			vertices.add(new Vertex(i+1));
		}
		MinHeapAdapter<Edge> heap = new MinHeapAdapter<Edge>(noOfConnectedComponents*noOfConnectedComponents);
		String[] strArr;
		while((str = br.readLine())!=null){
			strArr = str.split(" ");
			heap.insert(new Edge(vertices.get(Integer.parseInt(strArr[0])-1), vertices.get(Integer.parseInt(strArr[1])-1) , Integer.parseInt(strArr[2]) ));
		}
		Edge minEdge;

		while((minEdge = heap.extractMin())!=null){

			if(noOfConnectedComponents==kClusterNumber){
				break;
			}
			if(!uf.find(minEdge.getVertex1()).equals(uf.find(minEdge.getVertex2()))){
				noOfConnectedComponents--;
				/*	System.out.println(minEdge);
				System.out.println(uf.find(minEdge.getVertex1()));
				System.out.println(uf.find(minEdge.getVertex2()));*/
				uf.union(minEdge.getVertex1(), minEdge.getVertex2());
				mst.add(minEdge);
			}
		}
		while(uf.find(minEdge.getVertex1()).equals(uf.find(minEdge.getVertex2()))){
			minEdge = heap.extractMin();
		}
		System.out.println(minEdge);
		/*for(Edge e:mst){
			System.out.println(e);
		}*/
		printClusters();
	}
	
	private static void printClusters(){
		StringBuffer str;
		for(Vertex v:vertices){			
			if(v.getLeaderVertex().equals(v)){
				str = new StringBuffer();
				str.append(v+":[");
				for(UnionFindable v1:v.getSubelements()){
					str.append(v1+",");
				}
				str.setLength(str.length()-1);
				str.append("]");
				System.out.println(str);
			}
		}
	}

}
